package linear_list.leetcode.medium;

/**
 * @author Stark
 * @description 删除排序链表中的重复元素 II
 * 题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
 * @date 2022/4/7 19:11
 **/
public class Num82_DeleteDuplicates {
    int choice = 2;
    public ListNode deleteDuplicates(ListNode head) {
        if(choice == 1) {
            //非递归
            if (head == null || head.next == null)
                return head;
            //虚拟头结点
            ListNode dummyHead = new ListNode(0);
            ListNode cur = dummyHead, next = head.next;
            //标记是否有相同的结点
            boolean flag = true;
            while (next != null) {
                if (head.val != next.val) {
                    //当出现不相同的元素
                    if (flag)
                        //标志位为真,说明head指向的元素就只有一个
                        //将此结点连接到返回链表中
                        cur = cur.next = head;
                    head = next;
                    flag = true;
                } else {
                    //出现相同元素时,标志位为false,为了保证下一个元素不相同时,
                    //将上一个结点拼接到返回的链表中
                    flag = false;
                }
                next = next.next;
            }
            if (head.next == null)
                //走到最后只有一个结点时,说明该结点满足要求
                cur = cur.next = head;
            else
                //否则将返回链表截断
                cur.next = null;
            return dummyHead.next;
        }else if(choice == 2){
            if(head == null || head.next == null)
                return head;
            ListNode next = head.next;
            if(head.val == next.val){
                //当出现相同结点时
                while(next != null && head.val == next.val)
                    //让next一直向后走,直到找到结点和head.val不一样时
                    //将不相同的的结点递归下去,相同的结点都不要了
                    next = next.next;
                //此处不进行拼接操作,只是将重复的结点去除
                //如果最后几个结点都相同的话,递归的next为空
                //如果最后一个结点不同于其他结点,递归返回后还是该结点
                 head = deleteDuplicates(next);
            }else{
                //出现不相同的元素,就进行拼接操作
                head.next = deleteDuplicates(next);
            }
            return head;
        }else if(choice == 3){
            //非递归的很棒的写法
            if(head == null || head.next == null)
                return head;
            //使用虚拟头结点,直接将原链表拼接到虚拟头结点后
            //在原链表中进行操作
            ListNode dummyHead = new ListNode(0,head);
            ListNode prev = dummyHead,cur,next;
            while((cur = prev.next) != null && (next = cur.next) != null){
                if(cur.val != next.val){
                    //当出现前后两个结点的值不想等是
                    //让prev往后走,就保存原链表上的结点
                    prev = cur;
                    //继续往后判断后续结点
                    continue;
                }
                //出现相同元素,一直往后走找到不相同的结点
                //如果next走到空,说明 最后几个结点都是相同的,都不需要保存
                //则直接将原链表最后结点指向空
                while(next != null && cur.val == next.val){
                    next = next.next;
                }
                //这里只是将prev指向next结点,并没有保存该结点,后续还会判断该结点
                prev.next = next;
            }
            return dummyHead.next;
        }
        return null;
    }
}
